package arrays;

import java.util.Arrays;
import java.util.HashMap;

/**题目：
 *  给定一个数组，要求返回和为某个值的两个数字的下标
 *  y:  1 2 3 4 5 6 7           10
 *      [2,6]
 * @Author Gavin
 * @date 2021.12.07 21:39
 */
public class array_1 {
    //第一种就是暴力破解法，两重循环进行取值
    //Time: O(n^2) Space:O(1)
    public Integer[] solution(Integer[] array,int sum){
        for (int i = 0; i <array.length ; i++) {
            for (int j=i+1;j<array.length;j++){
                if(array[i]+array[j]==sum) return new Integer[]{i,j};
            }
        }
        return new Integer[]{-1,-1};
    }
    //第二种，需要借助hashmap来存储下标值，这样时间复杂度就变为了O(1)
    //Time:O(1) Space:O(n)
    public int[] solution(int[] array,int sum){
        HashMap<Integer,Integer> po=new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int needNum=sum-array[i];
            if(po.containsKey(needNum)){
                return new int[]{po.get(needNum),i};
            }
            po.put(array[i],i);//注意这里是比较关键的，把数组的值和下标存储到hashmap中
        }
        return new int[]{-1,-1};
    }
}
